Everything about Packing Problem totally explained
Packing problems are one area where
mathematics meets
puzzles (
recreational mathematics). Many of these problems stem from real-life packing problems.
In a packing problem, you're given:
- one or more (usually two- or three-dimensional) containers
- several 'goods', some or all of which must be packed into this container
Usually the packing must be without gaps or overlaps, but in some packing problems the overlapping (of goods with each other and/or with the boundary of the container) is allowed but should be minimised. In others, gaps are allowed, but overlaps are not (usually the total area of gaps has to be minimised).
Problems
There are many different types of packing problems. Usually they involve finding the maximum number of a certain shape that can be packed into a larger, perhaps different shape.
Sphere in Cuboid
A classic problem is the
sphere packing problem, where one must determine how many
spherical objects of given diameter
d can be packed into a
cuboid of size
a ×
b ×
c. This is one of the hardest problems in this category .
Packing Circles
There are many other problems involving packing circles into a particular shape of the smallest possible size.
Hexagonal packing
Circles (and their counterparts in other dimensions) can never be packed with 100% efficiency in
dimensions larger than one (in a one dimensional universe, circles merely consist of two points). That is, there will always be unused space if you're only packing circles. The most efficient way of packing circles,
hexagonal packing produces approximately 90% efficiency.
(External Link
)
Circles in circle
Some of the more non-trivial circle packing problems are packing unit circles into the smallest possible larger circle.
Proven Minimum Solutions:
| Number of circles |
Large circle radius |
| 1 |
1 |
| 2 |
2 |
| 3 |
2.154... |
| 4 |
2.414... |
| 5 |
2.701... |
| 6 |
3 |
Circles in square
Pack
n unit circles into the smallest possible square.
Proven Minimum Solutions:
| Number of circles |
Square size |
| 1 |
2 |
| 2 |
3.414... |
| 3 |
3.931... |
| 4 |
4 |
| 5 |
4.828... |
| 6 |
5.328... |
| 7 |
5.732... |
| 8 |
5.863 |
| 9 |
6 |
Circles in isosceles right triangle
Pack
n unit circles into the smallest possible isosceles right triangle (lengths shown are length of leg)
Proven Minimum Solutions:
| Number of circles |
Length |
| 1 |
3.414... |
| 2 |
4.828... |
| 3 |
5.414... |
| 4 |
6.242... |
| 5 |
7.146... |
| 6 |
7.414... |
| 7 |
8.181... |
| 9 |
9.071... |
| 10 |
9.414... |
Circles in equilateral triangle
Pack
n unit circles into the smallest possible equilateral triangle (lengths shown are side length).
Proven Minimum Solutions:
| Number of circles |
Length |
| 1 |
3.464... |
| 2 |
5.464... |
| 3 |
5.464... |
| 4 |
6.928... |
| 5 |
7.464... |
| 6 |
7.464... |
| 7 |
8.928... |
| 8 |
9.29... |
Circles in regular hexagon
Pack
n unit circles into the smallest possible regular hexagon (lengths shown are side length).
Proven Minimum Solutions:
| Number of circles |
Length |
| 1 |
1.154... |
| 2 |
2.154... |
| 3 |
2.309... |
Packing squares
Squares in square
A problem is the
square packing problem, where one must determine how many
squares of side 1 you can pack into a square of side
a. Obviously, here if
a is an integer, the answer is
a², but the precise, or even
asymptotic, amount of wasted space for
a a non-integer is open.
Proven Minimum Solutions:
| Number of squares |
Square size |
| 1 |
1 |
| 2 |
2 |
| 3 |
2 |
| 4 |
2 |
| 5 |
2.707 (2 + 2-1/2) |
| 6 |
3 |
| 7 |
3 |
| 8 |
3 |
| 9 |
3 |
| 10 |
3.707 (3 + 2-1/2) |
Other known results:
If you can pack n² − 2 squares in a square of side a, then a ≥ n.
The naive approach (side matches side) leaves wasted space of less than 2a + 1.
The wasted space is asymptotically o(a7/11).
The wasted space is not asymptotically o(a1/2).
Walter Stromquist proved that 11 unit squares can't be packed in a square of side less than 2+4*5-1/2.
Squares in circle
Pack n squares in the smallest possible circle.
Proven Minimum Solutions:
| Number of squares |
Radius of circle |
| 1 |
0.707... (2-1/2) |
| 2 |
1.118... |
Tiling
In this type of problem there are to be no gaps, nor overlaps. Most of the time this involves packing rectangles or polyominoes into a larger rectangle or other square-like shape.
Rectangles in rectangle
There are significant theorems on tiling rectangles (and cuboids) in rectangles (cuboids) with no gaps or overlaps:
» Klarner's Theorem: An a × b rectangle can be packed with 1 × n strips iff n | a or n | b.
de Bruijn's Theorem: A box can be packed with a harmonic brick a × a b × a b c if the box has dimensions a p × a b q × a b c r for some natural numbers p, q, r (for example, the box is a multiple of the brick.)
When tiling polyominoes, there are two possibilities. One is to tile all the same polyomino, the other possibility is to tile all the possible n-ominoes there are into a certain shape.
All the same polyominoes in a rectangle
Different polyominoes
A classic puzzle of this kind is pentomino, where the task is to arrange all twelve pentominoes into rectangles sized 3×20, 4×15, 5×12 or 6×10.
Further Information
Get more info on 'Packing Problem'.
|
External Link Exchanges
Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:
<a href="http://packing_problem.totallyexplained.com">Packing problem Totally Explained</a>
Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned. |
